#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//闭散列
namespace MyHashTable
{
	enum Status
	{
		EXIST,
		EMPTY,
		DELETE
	};
	template <class K,class V>
	struct Data
	{
		pair<K, V> _pair;
		Status _status = EMPTY;
	};

	template <class K,class V>
	class HashTable
	{
	public:
		//构造函数
		HashTable()
			:n(0)
			,v(10)
		{}
		//向类对象HashTable中插入数据的函数
		bool Insert(const pair<K, V>& p)
		{
			if (Find(p.first)) {
				return false;
			}
			auto size = v.size();
			if ((double)n / size >= 0.7) {
				size_t new_size = 2 * size;
				HashTable<K, V> tmp_hashtable;
				tmp_hashtable.v.resize(new_size);
				for (const auto& e : v) {
					tmp_hashtable.Insert(e._pair);
				}
				//将扩容后临时哈希表中的v于原来哈希表中的v交换
				v.swap(tmp_hashtable.v);
			}
			size_t pos = p.first % size;
			while (v[pos]._status == EXIST) {
				++pos;
				pos = pos % size;   //防止pos超过集合v的大小
			}
			//程序执行到这里说明找到了位置状态是EMPTY或DELETE的位置，可以进行插入
			v[pos]._pair = p;
			v[pos]._status = EXIST;
			++n;
			return true;
		}

		Data<K,V>* Find(const K& key)
		{
			size_t size = v.size();
			size_t pos = key % size;
			while (v[pos]._status != EMPTY) {
				if (v[pos]._status == EXIST && v[pos]._pair.first == key) { //保证了集合v中的pair键值对中的键值是唯一的
					return &v[pos];
				}
				++pos;
				pos = pos % size;
			}
			return nullptr;
		}
		bool Erase(const K& key)
		{
			//if (!Find(key)) {
			//	return false;
			//}
			//else {    //含key的键值对一定存在
			//	size_t size = v.size();
			//	size_t pos = key % size;
			//	while (v[pos] != key) {
			//		++pos;
			//		pos = pos % size;
			//	}
			//	v[pos]._status = DELETE;
			//	++n;
			//}
			//return true;
			Data<K, V>* target = Find(key);
			if (target) {
				target->_status = DELETE;
				--n;
				return true;
			}
			return false;
		}
		void print()
		{
			for (const auto& e : v) {
				if (EXIST == e._status) {
					cout << "key: " << e._pair.first << " value: " << e._pair.second << endl;
				}
			}
			cout << endl;
		}
	private:
		size_t n;
		vector<Data<K,V>> v;
	};
}

class Test
{
public:
	~Test()
	{
		cout << "~T()" << endl;
	}
};

Test func()
{
	Test t;
	return t;
}


//关于开散列哈希桶中的链表节点的删除
struct Node
{
	Node()
		:_val(0)
		,_next(nullptr)
	{}
	int _val;
	Node* _next;
};

bool deleteNode(Node** node, int val)
{
	//待删除链表中没有节点
	if (*node == nullptr) {
		return false;
	}
	if ((*node)->_val == val) {
		*node = (*node)->_next;
		return true;
	}
	else if ((*node)->_val != val && (*node)->_next == nullptr) {
		return false;
	}
	//待删除链表中的节点个数>=2，且待删除的节点不是链表第一个节点
	Node* front = *node;
	Node* cur = front->_next;
	Node* back = cur->_next;
	while (cur) {
		if (cur->_val == val) {
			front->_next = back;
			return true;
		}
		front = cur;
		cur = back;
		if (back) {
			back = back->_next;
		}
	}
	return false;
}

// static void func1()
// {
// 	static int a = 0;
// 	++a;
// 	cout << "a= " << a << endl;
// }

// void func2()
// {
// 	cout << "这是一个普通函数" << endl;
// }

// class Class
// {
// public:
// 	Class(int _n)
// 		:n(_n)
// 	{
// 		func1();
// 		func2();
// 	}
// 	void Func()
// 	{

// 	}
// private:
// 	int n;
// };



int main()
{
	func();
	MyHashTable::HashTable<int, int> hashtable;
	pair<int, int> p1 = std::make_pair(1, 5);
	pair<int, int> p2 = std::move(make_pair<int, int>(2, 7));
	hashtable.Insert(p1);
	hashtable.Insert(pair<int, int>(11, 2));
	hashtable.Insert(p2);
	hashtable.print();
	return 0;
}